package com.example.algorithm.interview;

/**
 * 招银笔试题1
 *
 * @description 从给定字符串找到字典序下最大子序列
 * @date 2023-12-16
 */
public class MaxDictionaryOrder {

    public static void main(String[] args) {
        String res = new MaxDictionaryOrder().maxDictionaryOrder("aabcbccacbbcbaaba");
        System.out.println(res);
    }

    public String maxDictionaryOrder(String s) {
        StringBuilder res = new StringBuilder();
        while (!s.isEmpty()) {
            int first = getFirst(s);
            res.append(s.charAt(first));
            if (first + 1 >= s.length()) {
                return res.toString();
            }
            s = s.substring(first + 1);
        }
        return res.toString();
    }

    private int getFirst(String s) {
        char[] charArray = s.toCharArray();
        int startCharIndex = 0;
        for (int i = 0; i < charArray.length; i++) {
            if (charArray[i] > charArray[startCharIndex]) {
                startCharIndex = i;
            }
        }
        return startCharIndex;
    }

}
